//最大流算法小结
//summary_of_maxflow_algorithm.cpp

//最大流的算法种类名目繁多，但是深究其核心技术则可以看出很多相通之处
//本文为前面所讲的各种最大流算法作一个小结

//最大流算法分为两大类算法：增广路径类算法，预留与推进类算法

//Ford-Fulkerson方法，增广路径类算法
//这类方法关键之处在于通过寻找一条增广路径来找出更多的流
//更容易理解的说法是：找出一条从源点到汇点的路径，它仍然拥有运输能力来运输流
//
//1)一般性标号算法
//用任意方法在残留网络中寻找一条增广路径，直到无法继续找出增广路径
//通过路径标号技术来记录路径，路径标号是所有增广路径类算法的基础技术
//2)容量缩放增广路径算法(Capacity-Scaling)
//重复以下步骤：
//从残留网络中用dfs寻找一条残留容量最大的增广路径
//该算法适合稀疏图
//3)Edmonds-Karp算法
//重复以下步骤：
//每次从残留网络中bfs寻找一条最短的增广路径
//适合稠密图
//4)Dinic算法，又称为阻塞流算法
//设置距离标号d(距离函数)，记录各节点到汇点的距离(拓扑顺序)
//重复以下步骤：
//用bfs方法得到残留网络当前的距离标号d
//使用距离标号(其实是一种dfs搜索)找出残留网络中的一条增广路径
//5)距离标号算法(Distance-Label)
//也称SAP(Shortest Augmenting Path)算法或者Improved-SAP(ISAP)算法
//重复以下步骤：
//使用距离标号找出残留网络中一条增广路径
//当需要时对某些节点进行重标记操作，即更改这些节点的d值
//
//根据命名来看，Edmonds-Karp和Dinic也属于SAP算法，它们也旨在寻找最短增广路径
//距离标号算法是最大流问题的终极解法，时间复杂度最小，相比预留与推进类算法更为流行

//预留与推进(Preflow-Push)类算法
//与增广路径类算法不同的是，该方法不去寻找一条从源点到汇点的路径
//而是将每个节点的流尽最大可能压入它的邻节点，好像源点是无穷无尽的泉眼
//最终将所有可能到达的流压入汇点即得到最大流
//
//该类算法普遍使用了两个技术：
//压入操作：将某节点的余流压入其相邻节点
//重标记操作：将某节点的d值更改为所有邻节点中d值最低的那个d值加1
//这两个技术也是距离标号的核心技术
//
//1)一般性压入与重标记算法(Generic-Push-Relabel)
//所有预留与推进类算法都使用了前置流这个技术，它是该类算法的核心技术
//重复以下步骤：
//从源点开始按任意顺序对所有节点进行压入或重标记操作
//直到所有节点没有更多的余流，汇点得到的流即为最大流
//2)重标记与前移算法(Relabel-to-Front)
//维护一个队列，初始时将所有节点按照拓扑顺序入队
//重复以下步骤：
//每次对队头节点进行排除(Discharge)，实际是压入与重标记，直到该节点余流为0
//若该过程中该节点即进行过重标记操作则重新将该节点入队头，否则出队
//其中重标记操作使用到了距离标号d
//3)最高标号预留与推进算法(Highest-Label Preflow-Push，简称HLPP)
//维护一个以距离标号d为优先级的队列，将所有节点入队
//重复以下步骤：
//每次对队头节点进行排除操作
//若该节点在排除操作中进行了重标记则将该节点重新入队，否则出队

//谈谈这些算法的命名：
//这些算法的命名问题也是我写本小结的初衷，明确这些算法之间的联系和区别
//在彻底的学习它们之后可以确定有些算法是完全相同的，或者本质上没有区别的
//我们用简单的字母来代替汉字名
//距离标号算法简称 DL，重标记与前移算法简称 RF，最高标号预留与推进算法简称 HLPP
//1)首先是 DL
//它有另外两个名字：SAP，ISAP，其实这三个名字是同一个算法
//2)其次是 RF 和 HLPP
//它们几乎是相同的算法，几乎没有区别，只是队列维护的说法不一样而已
//3)最后是 RF 和 DL
//网上有文档指出它们是相同的算法，但我经过学习之后认为：
//DL 与 算法导论中论述的 RF 有着很多联系和共通之处，但仍有很多不同的地方
//不仅仅是数据结构的不同，而是在前置流技术与增广路径上的本质区别

//各个算法的核心技术总结
//增广路径类算法：
//1)一般性标号算法：使用标号记录增广路径，所有增广路径算法都会使用这个技术
//2)容量缩放增广路径算法：使用dfs寻找容量最大的增广路径
//3)Edmonds-Karp算法：使用bfs寻找最短增广路径
//4)Dinic算法：使用距离标号寻找最短增广路径，使用bfs更新距离标号
//5)距离标号算法：使用距离标号寻找最短增广路径，使用重标记更新距离标号
//预留与推进类算法：
//1)一般性压入重标记算法：前置流技术，压入与重标记操作
//2)重标记与前移算法：使用距离标号对各节点进行压入与重标记操作
//3)最高标号算法：同重标记与前移算法
//
//增广路径类算法的基础技术是路径标号技术，就是通过设置一个数组来记录一条增广路径
//预留与推进类算法的核心技术是前置流技术，就是假想流网络中每个节点都可以存储无穷的流

//关键知识点
//添加反向边：
//当完全理解了最大流各种算法后读者会发现“添加反向边”在最大流算法中占有核心的位置
//容许边：
//它是最大流算法中的另一个同样重要的核心知识点
//算法优化：
//Gap Heuristic优化，邻接表优化，当前弧优化

//本文引用了“网络最大流问题算法小结[转]”，作者“龙豆”
//“网络流的Relabel-to-Front算法”，作者“scuxy06”
//“Max Flow2”，作者“GDUT_CHC”
//“距离标号最短增广路算法模板”，作者“冰糖葫芦”
//“最大流距离标号最短增广路算法”，作者“FallingFlowers”
